#include <stdio.h>
#include "tree.h"


//打印节点数据
void display_tree_data(TreeNode *t) {
    printf(" %d ", t->data);
}

//递归先序遍历二叉树
void pre_order_traverse(TreeNode *t) {
    if (t) {
        display_tree_data(t);
        pre_order_traverse(t->left_child);
        pre_order_traverse(t->right_child);
    }
}

//栈顶下标
int top = -1;

//出栈
void pop() {
    //如果i=-1,说明栈是空的
    if (top == -1) {
        return;
    }
    top--;
}

//入栈
void push(TreeNode **a, TreeNode *node) {
    a[++top] = node;
}

TreeNode *get_top(TreeNode **a) {
    return a[top];
}

//栈实现二叉树先序遍历
void stack_traverse(Tree tree) {
    //定义一个栈
    TreeNode *a[20];
    //入栈
    push(a, tree);

    while (top != -1) {
        TreeNode *node = a[top];
        pop();
        while (node) {
            display_tree_data(node);
            if (node->right_child) {
                push(a, node->right_child);
            }
            node = node->left_child;
        }
    }
}

int main() {
    Tree tree;
    create_tree(&tree);
    printf("递归先序遍历 \n");
    pre_order_traverse(tree);


    printf("\n");
    printf("栈实现先序遍历 \n");
    stack_traverse(tree);

    printf("\n");
    return 0;
}
